package 中等.贪心思想;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k
 * 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-k-digits/
 */
public class 移掉K位数字_402 {

    public static void main(String[] args) {

        System.out.println(removeKdigits("10", 2));

    }

    /**
     * 贪心+栈
     * 关键思路：
     * 对于长度相同的数字，同时从左至右扫描，相同位置的数的较小的数字整体较小
     * 也就是字典序比较
     * 那么总共要去除掉k个字符
     * 从左至右扫描，如果存在 num[i-1] > num[i] ,则删除 num[i-1] 位置的字符
     * 不存在，则字符串呈现非递减状态，那么最后一个数一定是最大的，删除最后一个字符
     * 重复k次
     * <p>
     * 使用栈来优化时间复杂度：
     * 1，如果当前元素比栈顶元素小则弹出栈顶元素，相当于删除一个字符
     * 2，如果遍历到最后，弹出的元素数量<k ，栈里面的元素是非递减排列，那么需要删除最后的 k-弹出数量
     */
    public static String removeKdigits(String num, int k) {
        Deque<Character> stack = new ArrayDeque<>();
        int curK = 0;
        for (int i = 0; i < num.length(); i++) {
            char cur = num.charAt(i);
            // 栈不为空，且栈顶元素大于当前元素，且删除数量小于k
            while (!stack.isEmpty() && stack.peekFirst() > cur && curK < k) {
                stack.pollFirst();
                curK++;
            }
            stack.addFirst(cur);
        }
        // 越靠近栈顶的元素越大，非递减排列，直接去除到后面的
        for (int i = 0; i < k - curK && !stack.isEmpty(); i++) {
            stack.pollFirst();
        }
        // 去除栈底部的0
        while (!stack.isEmpty() && stack.peekLast() == '0') {
            stack.pollLast();
        }

        if (stack.isEmpty()) return "0";  // 栈为空，说明全部都删掉了

        StringBuilder stringBuilder = new StringBuilder();

        while (!stack.isEmpty()) {
            stringBuilder.append(stack.pollLast());
        }
        return stringBuilder.toString();
    }

}
